package LeetCode;


import java.util.HashMap;

public class No437 {

    public int pathSum(TreeNode root, int targetSum){
        HashMap<Long,Integer> map = new HashMap<>();
        map.put(0L,1);
        return dfs(map,0,root,targetSum);
    }

    //map表中存放的是当前节点的前缀和，n代表的是已经有多少结果是符合的，在最后map需要减去一次当前前缀和，
    // 因为遍历是从底往上遍历的，相当于这种结果已经计算过了，不考虑这跳路线了，所以在map表中，需要减去这次的前缀和
    public int dfs(HashMap<Long,Integer> map, long curr, TreeNode root, int targetSum){
        if(root == null) return 0;
        int n= 0;
        curr += root.val;
        n = map.getOrDefault(curr-targetSum,0);
        map.put(curr,map.getOrDefault(curr,0)+1);
        n+=dfs(map,curr,root.left,targetSum);
        n+=dfs(map,curr,root.right,targetSum);
        map.put(curr,map.getOrDefault(curr,0)-1);
        return n;
    }

//    public int pathSum(TreeNode root, long targetSum) {
//        if(root==null) return 0;
//        int sum = rootSum(root,targetSum);
//        sum+=rootSum(root.left,targetSum-root.val);
//        sum+=rootSum(root.right,targetSum-root.val);
//        return sum;
//    }
//    public int rootSum(TreeNode root,long targetSum){
//        if(root == null) return 0;
//        int sum = 0;
//        if(root.val==targetSum) sum++;
//        if(root.left!=null) sum+=pathSum(root.left,targetSum-root.val);
//        if(root.right!=null) sum+=pathSum(root.right,targetSum-root.val);
//        return sum;
//    }
}
